/**
        给你一个树，请你 按中序遍历 重新排列树，使树中最左边的结点现在是树的根，
            并且每个结点没有左子结点，只有一个右子结点。


 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };


 */
class Solution {
public:
    vector<TreeNode*> NodeRecord;
    void Travel_In(TreeNode* node,vector<TreeNode*>&NodeRecord)
    {
        if(node == 0)
        {
            return ;
        }
        Travel_In(node->left,NodeRecord);
        NodeRecord.push_back(node);
        Travel_In(node->right,NodeRecord);
    }
    TreeNode* increasingBST(TreeNode* root) 
    {
        if(root == 0)
            return 0;
        Travel_In(root,NodeRecord);
        int Size = NodeRecord.size();
        for(int i=0;i<Size;i++)
        {
            NodeRecord[i]->left = 0;
            if(i+1<Size)
            {
                NodeRecord[i]->right = NodeRecord[i+1];
            }
            else
            {
                NodeRecord[i]->right = 0;
            }
        }
        return NodeRecord[0];

    }
};


/////////////////////////////////////////////////////////////
//在中序遍历中 进行 树 连接关系 的 调整

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* curNode = new TreeNode(-1);
    TreeNode * curNode2 = curNode;
    void Travel_In(TreeNode* node)
    {
        if(node == 0)
        {
            return ;
        }
        TreeNode* left = node->left;
        TreeNode* right = node->right;

        Travel_In(left);
        
        curNode->left = 0;
        curNode->right = node;
        curNode = node;

        Travel_In(right);
    }
    TreeNode* increasingBST(TreeNode* root) 
    {
        if(root == 0)
            return 0;
        Travel_In(root);
        return curNode2->right;

    }
};